package hero.mps.leet_code_23;

import java.util.PriorityQueue;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class MergeKthSortedList {

    public void printListNode(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        // 创建一个最小堆，用于存储链表节点，并根据节点的值进行排序
        PriorityQueue<ListNode> queue = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
        // 遍历每个链表
        for (ListNode list : lists) {
            // 当链表不为空时
            while (list != null) {
                // 将链表节点加入最小堆
                queue.add(list);
                // 移动到下一个节点
                list = list.next;
            }
        }
        // 创建一个虚拟头节点
        ListNode dummy = new ListNode(0);
        // 创建一个尾节点，初始指向虚拟头节点
        ListNode tail = dummy;
        // 当最小堆不为空时
        while (!queue.isEmpty()) {
            // 取出最小堆中的最小节点，并连接到当前链表末尾
            tail.next = queue.poll();
            // 将尾节点移动到当前链表的末尾
            tail = tail.next;
        }
        // 将尾节点的next指针置为null，表示链表结束
        tail.next = null;
        // 返回合并后的链表的头节点（虚拟头节点的下一个节点）
        return dummy.next;
    }

    public ListNode mergeKLists1(ListNode[] lists) {
        // 创建一个最小堆优先队列，根据节点的值进行排序
        PriorityQueue<ListNode> queue = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
        // 遍历所有链表
        for (ListNode list : lists) {
            // 如果链表不为空
            if (list != null) {
                // 将链表头节点加入优先队列
                queue.add(list);
            }
        }
        // 创建一个虚拟头节点
        ListNode dummy = new ListNode(0);
        // 尾节点指向虚拟头节点
        ListNode tail = dummy;
        // 当优先队列不为空时
        while (!queue.isEmpty()) {
            // 从优先队列中取出最小的节点
            ListNode minNode = queue.poll();
            // 将最小节点连接到当前链表的末尾
            tail.next = minNode;
            // 更新尾节点为当前最小节点
            tail = tail.next;
            // 如果最小节点还有下一个节点
            if (minNode.next != null) {
                // 将最小节点的下一个节点加入优先队列
                queue.add(minNode.next);
            }
        }
        // 将尾节点的next指针置为null，表示链表结束
        tail.next = null;
        // 返回合并后的链表的头节点（虚拟头节点的下一个节点）
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode list1 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
        ListNode list2 = new ListNode(2, new ListNode(4, new ListNode(6, new ListNode(7, new ListNode(8)))));
        ListNode list3 = new ListNode(5, new ListNode(8, new ListNode(9)));
        ListNode[] lists = new ListNode[]{list1, list2, list3};
        ListNode listNode = new MergeKthSortedList().mergeKLists1(lists);
        new MergeKthSortedList().printListNode(listNode);
    }
}
